Livré à domicile ! (d'après BAC ES, Liban 2019) - Remarques

• La première question de cet exercice n'est pas un problème très intéressant pour notre restaurateur... C'est plutôt une question que pourrait se poser une municipalité pour le ramassage des ordures ou l'entretien de la voirie.
  
• Concernant ce restaurateur, son problème serait plutôt de trouver le trajet le plus rapide (ou le plus court) qui passe chez chacun de ses clients. C'est un problème qui peut se résoudre par tâtonnements sur un graphe dont l'ordre est relativement faible comme ici, mais qui est très complexe en général, et qui est très connu des logisticiens sous le nom  de la « tournée du laitier » ou du « problème du voyageur de commerce ».
  

L'idée est de « barrer » progressivement les arêtes les plus coûteuses, en veillant à garder toujours un trajet possible, donc on commence par barrer   \(H_3 - H_8\) , puis  \(H_2 - H_3\) .
Il semble que la proposition suivante :  \(H_8 - H_7 - H_3 - H_6 - H_2 - H_1 - H_4 - H_5\)   en  \(67\) minutes soit bien optimisée. En trouverez-vous une meilleure ?